1. Technical Field of the Invention
The present invention relates in general to computer graphics and to vectorial image processing. The present invention more specifically concerns a method for the calculation of the bounding box of vectorial graphic shapes, in the context of vectorial image processing; by the term “bounding box” there is intended the smallest rectangle that circumscribes a digital graphic shape when the latter is positioned on a page (for instance a Web page), or however displayed on a screen, for instance the screen of a Personal Computer, or printed on a support of paper or other material.
2. Discussion of the State of the Art
The trend in modern developments in the field of Web and graphic interfaces is toward solutions of the declaratory type. The application software is written using more and more complex semantics and at a high level, so as to facilitate and to accelerate the project and implementation tasks. This is made possible thanks to the availability of engines for the interpretation of high-level and more and more sophisticated and complex languages. Many of these engines have been developed in the field of the Web, because the HTML (HyperText Markup Language) paradigm is the most common for the development of complex software applications. There are several examples of this type of engines. The Web browsers themselves, normally exploited by the users for the navigation in the World Wide Web, are interpreters of the HTML syntax (or of evolutions thereof), which is a specialization of the XML (eXtensible Markup Language) syntax. The Flash technology is another example, not limited to the graphic aspects, but also with functionality of application intelligence. XAML (eXtensible Application Markup Language) and XUL (XML User interface Language) by Microsoft and Mozilla, respectively, are other examples of engines that associate application logics to the creation of Graphical User Interfaces (GUI) through scripting languages capable of extending the functionalities, for instance allowing queries on remote databases, access to Web services or use of the network interfaces.
At the base of all these solutions there is a bidimensional (2D) vectorial graphic interpretation engine, capable of interpreting a syntax of the XML type transforming it into graphic primitives compliant with the used rendering libraries (in the field of computer graphics, the term “rendering” identifies the process of render, i.e. of generation of an image starting from a description thereof, for instance a mathematical description, provided in a determined language and interpreted by the graphic engine).
As known in the field, the vectorial modality provides for a generic digital graphic shape to be represented through one or more primitive graphic shapes (primitive curves), like for instance segments, circles etc. Every primitive curve is described through a respective mathematical equation on the base of parameters (so-called “control points”) apt to univocally identify it.
The vectorial representation modality of graphic shapes is advantageous since it operates with continuous functions and allows a total control of the primitives, and therefore of the graphic shapes to be represented. Particularly, by modifying the number and the position of the control points of the primitives it is possible to trace almost any graphic shape. Additionally, the vectorial representation modality occupies less memory resources compared to other representation modalities (like for instance the raster modality), and also the amount of data to be transferred (for instance through a network connection) is limited.
The graphic interpretation engines, particularly those of vectorial type, have the purpose of providing to the programmer high-level semantic constructions for the development of sophisticated graphic interfaces. The offered functionalities can be summarized in the following macrofamilies:                bidimensional shapes: elementary geometric images (primitives) are foreseen, like circles, rectangles with rounded edges, ellipsis, lines, polygons and polygonal lines (non-closed broken lines). Additionally, complex images are foreseen, known as “paths”, that are described as sets of elementary geometric images, with the addition of Bezier curves, with the purpose of allowing the greatest possible graphic flexibility. The concept of transformation is associated with the primitives, which in the 2D case is an affine 2D transformation;        “fill & stroke”: by this terms there are intended graphic primitives displayed using separate concepts of contour and filling. These constructions have vectorial characteristics different from each other: the contour is characterized by thickness, hatch, modes of junction and termination; the filling has instead associated therewith the concept of mode of filling (this is meaningful in particular for non-convex images). However, these constructions also have vectorial characteristics in common, known as “paint servers”, that identify the color by which the shape, that corresponds to the semantic construction, is drawn. The color can have simple characteristics, as in the case of solid color, or complex characteristics, as in the case of linear or radial color gradients. In this last case, the gradients are described by a vector that describes the direction of variation of the color, and by a list of “stop colors” that describes the trend of the colors in the form of a broken curve where the interpolation between two adjacent stop colors is linear.        video, images and audio: an important semantic functionality is the ability to insert and to check multimedia contents inside the displayed graphic scene;        animations: these are semantic constructions for modifying in a predetermined way the temporal evolution of the properties of the primitives;        interaction: the graphic engine is able to manage user events (like for instance movements of the mouse, clicks, inputs of keyboard commands) and to trigger the start, the end or in general to modify the temporal evolution of animations;        script and DOM (Document Object Model): the constructions described above, even being very powerful, cannot cover the whole range of possible functionalities needed by an author. The ability to describe through a program non-predefined behaviors is made possible by the ability of the graphic engine to execute interpreted high-level code, like Java or Javascript. The possibility to use interpreted code involves the availability of an API (Application Programming Interface) that the code can invoke for accessing in reading and writing the semantic information of the primitives. In order to be able to enter and update by means of a program the content of such information, the so-called DOM is generally used, which is a mode of representation of the documents structured as an object-oriented model.        
The dominant feature is the vectoriality: all the graphic primitives and the contour constructions (animations, interaction, scripting) are always described and used in vectorial mode.
There are many examples of standardized or proprietary engines that offer semantic functionalities referable to those described above; one of these is the Scalable Vector Graphics (SVG) engine of the W3C (World Wide Web Consortium).
In general, a vectorial graphic engine receives a description of a vectorial graphic scene to be drawn. The graphic scene is normally described in XML and it is composed by a hierarchy of nodes (father and children) represented by a tree of inheritance. The nodes can be “container” type nodes, that is, they are not susceptible of a graphic representation but act as containers of other nodes, or the nodes can be shapes or graphic primitives, that is, they do have a graphic representation.
A problem of significant complexity is the calculation of the bounding box of a graphic primitive. This functionality is essential for the following reasons:                use by the interpreted script code: in order to be able to manipulate the properties of complex primitives, or of groups of complex primitives, the calculation of the bounding box needs to be made available on the API of the DOM, that allows the author to check the encumbrance of the complex and composed primitives;        vectorial features expressed in relative way: the gradients of the vectors can for instance be represented in the system of coordinates of the complex primitive (instead of being represented in the user reference system used by the primitive that exploits it, or even in document coordinates);        manipulation of the graphic objects through visual editing tools of the WYSIWYG (What You See Is What You Get) type: the movement, the rotation, the scaling of the dimensions of the graphic primitive inside the scene through visual paradigms using pointing tools like a mouse and a keyboard usually exploit the concept of bounding box drawn around to the primitive(s) selected by the user at a given time.        
The bounding box, also known in literature as “Minimum Bounding Rectangle” (MBR), has the followings features:                it has to be calculated as the smallest rectangle that contains the complex image without intersecting it;        it shall not take into account the transformations that the complex image receives in inheritance from the primitives that contain it. This is due to the strongly hierarchical semantics of SVG. A primitive can be contained by other elements (fathers). The propagation of the node properties from the father node to the child node follows different rules depending on the properties: in the case of affine transformations, the applied rule is the accumulation.        
The bounding box information is not strictly linked to the current drawing of the scene. Particularly, the necessity of providing the bounding box information also to the script code that is executed inside the scene foresees that the calculation of the bounding box might be requested also in respect of primitives that are not subsequently visible, which are not in the drawing branch of the tree that describes the scene, or that have a series of inherited parameters that do not follow the inheritance rules of the tree. For instance, it may be necessary to have the bounding box of a group of primitives taking into account the transformation inherited from their fathers. This means having available the encumbrance of the complex primitive before every transformation that projects it into the general scene. Another example that shows how it may be possible to require the calculation of the bounding box for composed primitives that are not visible is the case of the creation of a description branch of the scene through a program (through a script code): in this case the code can create a branch of description of the scene and it may require the bounding box thereof before this is inserted in the main tree.
From a functional point of view, the task of calculating the bounding box of a complex primitive is to be associated with the part of the graphic engine that manages the drawing, that is, that phase that transforms the information present in the tree description of the scene into bidimensional drawing, graphic primitives.
In modern rendering techniques, due to the increasing complexity of the scenes to be drawn, the hardware acceleration made possible by the graphic processors (for instance, Graphic Processing Unit—GPU) is exploited. Machines devoted to the management of the graphics are fed with series of primitives in a complex processing chain (a pipeline). Many types of processing pipelines exist, the most common being those used in three-dimensional videogames through APIs known as Direct3D (Microsoft) and OpenGL (Linux etc.). In general, the rendering process is under the control of a processing unit different from the main CPU, or however under the control of a processing task different from that managing the remaining of the application.
In general, as for instance described in S. Conversy J. D. Fekete, “The svgl toolkit: enabling fast rendering of rich 2D graphics”, Technical Report 02/1/INFO, Ecole des Mines de Nantes, 2002, in order to be able to require to the renderer (the hardware processing unit or the firmware or software task that performs the operations necessary for the rendering) to calculate the bounding box, it is necessary to send thereto the list of the primitives and the related properties, and then wait for the renderer task to take over the information, and feed the draw processing pipeline; the processing pipeline shall thereafter execute all the operations waiting in the queue and eventually it provides the result. Particularly, for calculating the bounding box the renderer simulates the process of rendering of the branch of tree inside which there is the primitive, as if the renderer should display the graphic shape described by the primitive, even if the display on the screen of the primitive is not necessary.
Since, normally, the processing pipelines are exclusively able to draw pixels and not primitives expressed in vectorial way, it is necessary (through software or using hardware functionalities provided for in the pipeline) to decompose the vectorial primitive in simple linear primitives (for example lines or triangles) compatible with the way of operation of the pipeline; this operation is known as tessellation. After the tessellation, the calculation of the bounding box is relatively simple, since it is a by-product of the tessellation operation results (consisting in the identification of the minimum and of the maximum—in the selected system of coordinates—among all the generated vertexes).
U.S. Pat. No. 6,512,847 shows a technique for the calculation of a frame around a Bezier curve. The frame corresponds to a Bezier curve that approximates the trend of the original Bezier curve spaced apart of an arbitrary distance. In this case, an approximation is employed that eventually imposes the definition of a “mid point” inside the curve through known algorithms and the related calculation of the new “control points” decomposing the curve in sub-curves of lesser length.
WO 2004/100071 proposes a method for the analytical deformation of Bezier curves; the deformation is set through an interaction with the user keeping fixed the initial and final controls points and sectioning or joining different curves for best approximating the desired deformation. The requisite of providing curves parallel to the original one is not considered.